package com.congee02;

import java.util.*;

public class DeleteAndEarn {

    public int deleteAndEarn(int[] nums) {

        int max = 0;
        for (int x : nums) {
            max = Math.max(max, x);
        }

        int[] hash = new int[max + 1];
        for (int x : nums) {
            hash[x] ++;
        }

        return process(hash, 1, 0);
    }

    private int process(int[] hash, int index, int got) {
        if (index == hash.length) {
            return got;
        }

        boolean right = index + 1 < hash.length;

        int ret = 0;
        // delete and earn
        int t1 = hash[index - 1];
        int t2 = 0;
        if (right) t2 = hash[index + 1];
        hash[index - 1] = 0;
        if (right) hash[index + 1] = 0;
        int p1 = process(hash, index + 1, got + hash[index] * index);

        hash[index - 1] = t1;
        if (right) hash[index + 1] = t2;

        // not delete
        int p2 = process(hash, index + 1, got);

        return Math.max(p1, p2);
    }



}
